package com.sx.sx1.lintcode.day717;

public class LC891 {

    static class Solution {
        /**
         * @param s: a string
         * @return: whether you can make s a palindrome by deleting at most one character
         */
        public boolean validPalindrome(String s) {
            // Write your code here
            int n = s.length();
            int left = 0;
            int right = n - 1;

            while (left <= right) {
                if (s.charAt(left) != s.charAt(right)) {
                    int bak1 = left;
                    int bak2= right;
                    boolean zuo = true;
                    left+=1;
                    while (left<=right) { //尝试删除bak1处的字符
                        if (s.charAt(left) != s.charAt(right)) {
                            zuo= false;
                            break;
                        }
                        left++;
                        right--;
                    }

                   if(!zuo) { //如果删除左边不行，尝试删除右边bak2处的字符
                       left= bak1;
                       right = bak2-1;
                       while (left<=right) { //尝试删除bak处的字符
                           if (s.charAt(left) != s.charAt(right)) {
                             return false;
                           }
                           left++;
                           right--;
                       }
                   } else{
                       return true;
                   }
                }
                left++;
                right--;
            }

            return true;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.validPalindrome("aba"));
        System.out.println(obj.validPalindrome("abca"));
        System.out.println(obj.validPalindrome("abc"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有214条未读消息，请及时查看
891 · 有效回文串（二）
算法
中等
通过率
53%

题目
题解70
笔记
讨论99+
排名
记录
描述
给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


给定的字符串只包含小写字母
字符串的长度最大为 50000
样例
样例 1:

输入: s = "aba"
输出: true
解释: 原本就是回文串
样例 2:

输入: s = "abca"
输出: true
解释: 删除 'b' 或 'c'
样例 3:

输入: s = "abc"
输出: false
解释: 删除任何一个字符都不能使之变成回文串
相关知识
学习《2024年7月北美大厂最新面试真题精讲》课程中的3.9Meta：最新面试精选005相关内容 ，了解更多相关知识！
标签
企业
网易
Facebook
相关题目

415
有效回文串
中等

491
回文数
简单

627
最长回文串
简单

678
最短回文串
中等

3809
有效回文串（三）
困难

3825
有效回文串（四）
简单
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */